Módulo Redes Sociales: Sesión 3

Departamento de Estadística

Universidad Nacional de Colombia, Sede Bogotá

Equipo de trabajo

Docente del módulo

Profesor Juan Camilo Sosa Martinez (Cohorte 1) jcsosam@unal.edu.co

Monitor del módulo

Bryan Camilo Riveros Guarnizo (Cohorte 1) briveros@unal.edu.co

Código a ejecutar para empezar (de clic en donde en dice “Code”, para desplegar el código, y luego copie y pegue en una sesión abierta de R):

Code

# cambia idioma de la consola de R a español:
Sys.setenv(LANG="es")
# usar 2 cifras significativas y tiende a evitar 
# notación científica (ver ayuda de función: `options`): 
options(digits = 2, scipen = 999) 
# cargar librerías: 
if(!require(igraph)){
  install.packages("igraph"); library(igraph)}
if(!require(sand)){
  install.packages("sand"); library(sand)}

Grafos y subgrafos

Grafos

Un grafo G = (V, E) es una estructura que consiste de un conjunto de vértices (nodos) V y de un conjunto de aristas (enlaces) E, donde los elementos de E son parejas de la forma e=\{u,v\}, con u,v\in V.

Subgrafos

Un grafo G'=(V',E') es un subgrafo de G=(V,E) si V'\subset V y E'\subset E.

Isomorfismo

Dos grafos que son equivalentes estructuralmente (a pesar de las etiquetas de los vértices) se denominan isomorfos.

Dos grafos G_1 = (V_1, E_1) y G_2 = (V_2, E_2) son isomorfos, lo que se escribe G_1 \equiv G_2, si existe una biyección \varphi:V_1\longrightarrow V_2 tal que \{u,v\}\in E_1 si y solo si \{\varphi(u),\varphi(v)\}\in E_2.

Ejemplo

Si G_1 \equiv G_2, entonces |V_1| = |V_2| y |E_1| = |E_2|.

Si |V_1| \neq |V_2| o |E_1| \neq |E_2|, entonces G_1 \not\equiv G_2.

Si G_1 \equiv G_2 y \{u,v\}\notin E_1, entonces \{\varphi(u),\varphi(v)\}\notin E_2.

Ejercicio

¿G_1 y G_2 son isomorfos?

Ejemplo Práctico

Creación grafos

suppressMessages(suppressWarnings(library(igraph)))

g1 <- graph_from_literal(0-1, 1-2, 2-3, 3-4, 4-0)
g2 <- graph_from_literal(a-c, a-d, b-d, b-e, c-e)

Son isomorfos?

# 'method'
# auto: Selecciona el mejor procedimiento
# direct: Si el grafo tiene tres o cuatro vértices
# vf2: Si el grafo es dirigido
# bliss: En cualquier otro caso

isomorphic(g1, g2, method = "auto")

[1] TRUE

Visualización

# visualización
set.seed(123)
par(mfrow = c(1,2))
plot(g1, vertex.size = 15, main = "Grafo 1")
plot(g2, vertex.size = 15, main = "Grafo 2")

Adyacencia

Vértives adyacentes

Se dice que dos vértices u, v \in V son adyacentes (adjacent), lo que se denota con u\sim v, si u y v están conectados por alguna arista de E.
Vértives asilados

Un vértice v\in V se llama asilado (isolated) si v\not\sim u para todo u\in V.

Un grafo se puede almacenar por medio de una matriz de aristas y una lista de vértices aislados.
Vértices incidentes

Un vértice v \in V es incidente (incident) en una arista e\in E si e = \{v,u\} para algún u\in V.

Grado

El grado (degree) del vértice v\in V se define como el número de aristas incidentes en v.
Para dígrafos, el grado de entrada (in-degree) y el grado de salida (out-degree) del vértice v\in V se definen como el número de aristas que apuntan hacia dentro y hacia fuera de v, respectivamente.

Ejemplo

Creación de la red no dirigida

g <- graph_from_literal(1-2, 1-3, 2-3, 2-4, 3-5, 4-5, 4-6, 4-7, 5-6, 6-7)

Vecinos del vértice 1

neighbors(graph = g, v = 1)

+ 2/7 vertices, named, from 0ab6204:
[1] 2 3

Grados

degree(graph = g)

1 2 3 4 5 6 7 
2 3 3 4 3 3 2

Visualización

set.seed(123)
plot(g)

Ejemplo

# red dirigida
dg <- graph_from_literal(1-+2, 1-+3, 2++3)

# grado de entrada
degree(graph = dg, mode = "in")

1 2 3 
0 2 2

# grado de salida
degree(graph = dg, mode = "out")

1 2 3 
2 1 1

# visualización
set.seed(123)
plot(dg)

Movimiento

Caminata:

Una caminata (walk) de v_0 a v_\ell de longitud \ell es una secuencia alternante \{v_0,e_1,v_1,e_2,v_2,\ldots,v_{\ell-1},e_\ell,v_\ell\} en la que los puntos extremos de e_i son \{v_{i-1}, v_i\}, con i=1,\ldots,\ell (se pueden repetir vértices y aristas).

Ejemplo

1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 3\, es una caminata abierta.
1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 3\rightarrow 1\, es una caminata cerrada.

Sendero

Un sendero (trail) es una caminata abierta sin aristas repetidas (se pueden repetir vértices).

1\rightarrow 3\rightarrow 8\rightarrow 6\rightarrow 3\rightarrow 2\, es un sendero.

Circuito

Un circuito (circuit) es una caminata cerrada sin aristas repetidas (se pueden repetir vértices).

1\rightarrow 2\rightarrow 4\rightarrow 3\rightarrow 6\rightarrow 8\rightarrow 3\rightarrow 1\, es un circuito.

Ciclo

Un ciclo (cycle) es una caminata cerrada con al menos tres aristas no repetidas y vértices intermedios distintos.

1\rightarrow 2\rightarrow 4\rightarrow 3\rightarrow 1\, es un ciclo.

Los grafos que no contienen ciclos se denominan acíclicos (acycle).

Conectividad

Se dice que un vértice v es accesible (reachable) desde otro vértice u si existe una caminata desde u hasta v.
Se dice que un grafo está conectado (connected) si cada vértice es accesible desde todos los demás.
Una componente (component) de un grafo es un subgrafo conectado maximalmente, i.e., un subgrafo al que añadirle cualquier otro vértice arruina la conectividad.

Ejemplo: grafos conectados con 5 vértices

Ejemplo

Creación de la red no dirigida

g <- graph_from_literal(1-7, 2-7, 2-4, 3-6, 4-7, 5-11, 6-12, 7-8, 7-9, 7-10)

Es conectado?

is_connected(g)

[1] FALSE

Componentes

clusters(g)

$membership
 1  7  2  4  3  6  5 11 12  8  9 10 
 1  1  1  1  2  2  3  3  2  1  1  1 

$csize
[1] 7 3 2

$no
[1] 3

Visualización

set.seed(123)
plot(g)

Tipo de conexión

Un digrafo está conectado débilmente (weakly connected) si el grafo subyacente (resultado de remover la direccionalidad) está conectado.
Un digrafo está conectado fuertemente (strongly connected) si cada vértice es accesible desde todos los demás mediante una caminata dirigida.

Ejemplo

Creació de la red dirigida

dg <- graph_from_literal(1-+2, 1-+3, 2++3)

Esconectado débilmente?

is_connected(graph = dg, mode = "weak")

[1] TRUE

Es conectado fuertemente?

is_connected(graph = dg, mode = "strong")

[1] FALSE

Visualización

set.seed(123)
plot(dg)

Distancia

La distancia geodésica entre dos vértices de un grafo es la longitud de la caminata más corta entre los vértices.
La distancia se define como infinito si no existen caminatas entre los vértices.
El valor de la distancia más grande de un grafo se llama diámetro del grafo.
La distancia geodésica promedio es una medida del grado de separación de los vértices.

Ejemplo

Creación de la red no dirigida

g <- graph_from_literal(1-2, 1-3, 2-3, 2-4, 3-5, 4-5, 4-6, 4-7, 5-6, 6-7)

Distancia

distances(graph = g, v = 1, to = 6)

  6
1 3

Caminata

shortest_paths(graph = g, from = 1, to = 6)$vpath

[[1]]
+ 4/7 vertices, named, from 0b2fc97:
[1] 1 2 4 6

Visualización

set.seed(123)
plot(g)

Caminatas

all_shortest_paths(graph = g, from = 1, to = 6)$res

[[1]]
+ 4/7 vertices, named, from 0b2fc97:
[1] 1 3 5 6

[[2]]
+ 4/7 vertices, named, from 0b2fc97:
[1] 1 2 4 6

Distancias

(D <- distances(graph = g, v = V(g), to = V(g)))

  1 2 3 4 5 6 7
1 0 1 1 2 2 3 3
2 1 0 1 1 2 2 2
3 1 1 0 2 1 2 3
4 2 1 2 0 1 1 1
5 2 2 1 1 0 1 2
6 3 2 2 1 1 0 1
7 3 2 3 1 2 1 0

Diámetro

diameter(g)

[1] 3

Diámetro (otra manera)

max(D[lower.tri(D)])

[1] 3

Sendero del diámetro

(d <- get_diameter(g))

+ 4/7 vertices, named, from 0b2fc97:
[1] 1 2 4 6

Visualización del diámetro

V(g)$color <- "white"
E(g)$color <- "grey"
E(g)$width <- 1
V(g)[d]$color <- "royalblue"
E(g, path = d)$color <- "royalblue"
E(g, path = d)$width <- 2
set.seed(123)
plot(g)

Distancia geodésica promedio

mean_distance(g)

[1] 1.7

Distancia geodésica promedio (otra manera)

mean(D[lower.tri(D)])

[1] 1.7

Distribución de las distancias

distance_table(g)

$res
[1] 10  8  3

$unconnected
[1] 0

Visualización

senderos <- distance_table(g)$res
names(senderos) <- 1:length(senderos)
barplot(prop.table(senderos), xlab = "Distancia geodésica", ylab = "F. Relativa", border = "grey", col = "grey", main = "Distribución de distancias geodésicas")